package com.river.springbootdemo.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 快速排序
 *
 * @author cxy
 */
public class QuickSort {
    public static List<Integer> quickSort(List<Integer> arr) {
        if (arr.size() < 2) {
            return arr;
        } else {
            int base = arr.get(0);
            List<Integer> lessArr = new ArrayList<>();
            List<Integer> greatArr = new ArrayList<>();
            for (int i = 1; i < arr.size(); i++) {
                Integer equal = arr.get(i);
                if (equal > base) {
                    greatArr.add(equal);
                } else {
                    lessArr.add(equal);
                }
            }
            List<Integer> resultList = new ArrayList<>(quickSort(lessArr));
            resultList.add(base);
            resultList.addAll(quickSort(greatArr));
            return resultList;
        }
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(5, 67, 23, 8, 2, 4, 45, 43, 2, 5, 2, 65, 21, 7765, 23, 54, 23);
        System.out.println(list);
        System.out.println(quickSort(list));
        System.out.println(list);
    }

}
